/*
提交链接:https://leetcode.cn/problems/longest-palindromic-substring/description/
5. [最长回文子串]
赖德檀 2024/12/04
*/
 
class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        string ss; 
        int maxx=0;
        vector<vector<bool>>dp(n,vector<bool>(n,false));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(j-i<=1)
                    {
                        dp[i][j]=true;
                    }
                    else if(dp[i+1][j-1])
                    {
                        dp[i][j]=true;
                    }
                    if(maxx<j-i+1&&dp[i][j])
                    {
                        maxx=j-i+1;
                        ss=s.substr(i,j-i+1);
                    }
                }
            }
        }
        return ss;
    }
};